#ifndef DGRAPH_H_INCLUDED
#define DGRAPH_H_INCLUDED

#include "DTree.h"
#include "headers.h"

#include <queue>
#include <hash_map>
using namespace std;
using namespace __gnu_cxx;

struct Vertex {
	int _ID; // vid: 0, 1, ..., N-1 for N vertices
	int _PreN;
	int _DFLN;
	int _SupDFLN; // Maximal
	//int _IntBeg;    // beginning of interval label
	//int _IntEnd;    // end of interval label
	int _TopoID; // topological order
	bool _visited;

	int _SupPreN;

	int level;
};

typedef vector<int> EdgeList;
typedef vector<Vertex> VertexList;

//          vid  out NTE edges
typedef map<int, EdgeList> LNTEList; // List of long NTE
typedef map<int, EdgeList> SNTEList; // List of short NTE
//typedef map<int, EdgeList> NTEList;
//          vid  vid
//typedef map<int, int> SNTEList; // after reduction

struct InOutEdgeList {
	EdgeList _inList;
	EdgeList _outList;
};

typedef vector<InOutEdgeList> GRAPH;

class DGraph {
private:
	GRAPH _G;
	VertexList _VL;
	int _N; // number of vertices
	bool opt;
	vector<int> roots;


	//   int _M; // number of edges

public:
	hash_set<int> lnte_nodes;
	DTree _tree;
//	NTEList _NTE;
	LNTEList _longNTE;
	SNTEList _shortNTE;

public:
	DGraph();
	DGraph(int N);
	DGraph(istream& in);
	DGraph(GRAPH&, VertexList&);
	DGraph(/*hash_map*/map<int, vector<int> >& inlist, /*hash_map*/map<int,
			vector<int> >& outlist);
	/*
	 Graph(GRA&, VertexList&);
	 Graph(istream&);
	 */
	~DGraph();
	/*
	 void read_graph(istream&);
	 void writeGraph(ostream&);
	 void printGraph();
	 */
	void clear();

	void add_vertex(int vid);
	bool add_edge(int src, int trg);
	bool delete_edge(int src, int trg);
	int number_of_vertices();
	int number_of_edges();
	VertexList& get_vertices();
	VertexList get_vertices_withoutrefer();
	EdgeList& edges_from(int vid);
	EdgeList& edges_to(int vid);

	int out_degree_of(int vid);
	int in_degree_of(int vid);

	vector<int> get_roots();
	bool has_edge(int src, int trg);
	DGraph& operator=(const DGraph& graph);
	Vertex& operator[](const int vid);

	void read_graph(istream& in);
	void write_graph(ostream& out);

	DTree& get_tree();
//	NTEList& get_NTEs();
	SNTEList& get_short_NTEs();
	LNTEList& get_long_NTEs();
	void write_tree(ostream& out);
	void write_NTEs(ostream& out);
	void write_short_NTEs(ostream& out);
	void write_long_NTEs(ostream& out);

	void extract(/*hash_map*/map<int, vector<int> >& inlist, /*hash_map*/map<
			int, vector<int> >& outlist);

	bool reachViaTree(int i, int j);
	/*
	 Graph(hash_map<int,vector<int> >& inlist, hash_map<int,vector<int> >& outlist);

	 void printMap(hash_map<int,vector<int> >& inlist, hash_map<int,vector<int> >& outlist);
	 */

	queue<int> init_roots_degrees(int* outDegrees);
	void rearrange(hash_map<int, int>& opt_order);

};

#endif // DGRAPH_H_INCLUDED
